package B.链表;
/**
 * 此题中 寻找相交节点 是节点相等 而不是节点数值相等
 */

import java.util.HashMap;
import java.util.Map;

public class _160_相交链表 {

    /**
     * 自解 借用多余空间--没做出来。。===解决：存的是节点
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {


        Map<Integer,ListNode> map = new HashMap<>();
        int count =0;
        while (headA != null){
            map.put(count,headA);
            headA = headA.next;
            count++;
        }

        while (headB !=null){

            if (map.containsValue(headB)  ){
                return headB;
            }else {
                headB = headB.next;
            }
        }
        return null;
    }

    /**
     * 双指针法！！！牛逼
     *设置两个头结点 分别遍历两个链表 如果有交点必然最终的数值相同
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        ListNode p1 = headA;
        ListNode p2 = headB;

        while (p1!=p2){
            p1 = p1.next;
            p2 = p2.next;

            if (p1 == null && p2 == null){
                return null;
            }
            if (p1 == null){
                p1 = headB;
            }
            if (p2 == null){
                p2 = headA;
            }

        }
        return p1;
    }

    /**
     * 统计长度 把前面多的走过去
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {

        int lthLong = 0;

        if (lenth(headA)>=lenth(headB)){
            lthLong = lenth(headA)-lenth(headB);
            while (lthLong>0){
                headA = headA.next;
                lthLong--;
            }
        }else {
            lthLong = lenth(headB)-lenth(headA);
            while (lthLong>0){
                headB = headB.next;
                lthLong--;
            }
        }

        //直接比较本节点就好 不用对比下一个， 理解为指针
        //然后开始比较，如果他俩不相等就一直往下走
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        //走到最后，最终会有两种可能，一种是headA为空，
        //也就是说他们俩不相交。还有一种可能就是headA
        //不为空，也就是说headA就是他们的交点
        return headA;



    }
    //封装一个用来计算长度的函数
    public int lenth(ListNode head){
        int count =0;
        while (head != null){
            count++;
            head = head.next;
        }
        return count;
    }

}
